#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define inf 10000
typedef struct graph{
    vector<char> point;
    vector<vector<int>>mark;
    int pnum;
    int egnum;
}graph;
void creat(graph &a){
    a.egnum=0;
    a.pnum=0;
}
vector<bool>visdfs;
vector<bool>visbfs;
void pointcreat(graph &a){
    cout<<"请输入输入点的个数";
    int n;
    cin>>n;
    a.pnum=n;
    for(int i=0;i<n;i++){
        cout<<"请输入第"<<i+1<<"个结点的值";
        char ch;
        cin>>ch;
        a.point.push_back(ch);
    }
}
void createdge(graph &a){
    cout<<"请输入添加边的个数";
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cout<<"请输入第"<<i+1<<"个边信息";
        int c,b,v;
        cin>>b>>c>>v;
        if(a.mark[b][c]==inf){
            a.egnum++;
        }
        a.mark[b][c]=v;
    }
}
void init(graph &a){
    a.mark.resize(a.pnum);
    for(int i=0;i<a.pnum;i++){
        a.mark[i].resize(a.pnum);
        for(int j=0;j<a.pnum;j++){
            a.mark[i][j]=inf;
        }
    }
}
void dfs(graph a,int w){
    visdfs[w]=1;
    cout<<a.point[w];
    for(int i=0;i<a.pnum;i++){
        if(a.mark[w][i]==1&&visdfs[i]==0){
            dfs(a,i);
        }
    }
}
void bfs(graph a){
    queue<int>q;
    cout<<"请输入开始的位置值";
    int data;
    cin>>data;
    q.push(data);
    cout<<a.point[data];
    while(!q.empty()){
        int n=q.front();
        q.pop();
        for(int i=0;i<a.pnum;i++){
            if(a.mark[n][i]==1&&visbfs[i]==0){
                cout<<a.point[i];
                q.push(i);
                visbfs[i]=1;
            }
        }
    }
}
vector<bool> ch;
vector<int>  pre;
vector<int> va;
int checkmin(vector<int> a){
    int max1=inf;
    int vist=-1;
    for(int i=0;i<va.size();i++){
        if(max1>va[i]&&ch[i]==0){
            vist=i;
            max1=va[i];
        }
    }
    if(vist==-1) return vist;
    ch[vist]=true;
    return vist;
}

void disirke(graph a){
    ch.resize(a.pnum,0);
    pre.resize(a.pnum);
    va.resize(a.pnum);
    for(int i=0;i<a.pnum;i++){
        va[i]=a.mark[0][i];
        pre[i]=0;
    }
    for(int i=0;i<a.pnum;i++){
        int t=checkmin(va);
        if(t==-1)return;
        for(int j=0;j<a.pnum;j++){
            if(!ch[j]&&va[j]>va[t]+a.mark[t][j]){
                va[j]=va[t]+a.mark[t][j];
                pre[j]=t;
            }
        }
    }
}
void display(vector<int>a){
    for(int i=0;i<a.size();i++)
        cout<<"第"<<i+1<<"个最短路径为"<<a[i]<<endl;
}
int main(){
    cout<<"开始创建图"<<endl;
    graph a;
    creat(a);
    cout<<"创建成功"<<endl;
    cout<<"开始创建各个节点"<<endl;
    pointcreat(a);
    cout<<"创建成功"<<endl;
    cout<<"开始初始化邻接矩阵"<<endl;
    init(a);
    cout<<"初始化成功"<<endl;
    cout<<"开始创建边";
    createdge(a);
    cout<<"创建成功";
    disirke(a);
    cout<<"执行成功";
    display(va);
    for(int i=0;i<a.pnum;i++){
        cout<<pre[i];
    }
    return 0;
}